package simple;

import data.ListNode;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/8/2 10:11
 */
public class No234_回文链表 {
    public static void main(String[] args) {
        Solution234 solution234 = new Solution234();
        ListNode head = new ListNode(1);
        boolean palindrome = solution234.isPalindrome(head);
        System.out.println(palindrome);
    }
}

class Solution234 {
    public boolean isPalindrome(ListNode head) {
        // 快慢指针反转链表
        // 时间复杂度O(n) 空间复杂度O(1)
        //头法
        ListNode realHead = new ListNode(-1);
        realHead.next = head;
        //保存头,用于slow回溯
        ListNode realHeadCp = realHead;

        ListNode slow = realHead;
        ListNode fast = realHead;

        //获取slow位置
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //slow 位置确定,开始反转


        if (fast == null) {
            //说明链表长度奇数
            fast = reverseList(slow);
            //回溯slow
            slow = realHeadCp.next;
        } else if (fast.next == null) {
            //说明链表长度偶数
            fast = reverseList(slow.next);
            //回溯slow
            slow = realHeadCp.next;
        }
        //判断是否回文
        while (fast != null) {
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    //将data反转
    public ListNode reverseList(ListNode data) {
        ListNode red = null;
        ListNode green = data;
        while (green != null) {
            ListNode yellow = green.next;
            green.next = red;
            red = green;
            green = yellow;
        }
        return red;
    }

}



    //public boolean isPalindrome(ListNode head) {
    //    //转集合list,双指针 No125:回文字符串
    //    List<BigDecimal> list = new ArrayList<>();
    //    //链表放集合
    //    while (head != null) {
    //        list.add(new BigDecimal(head.val));
    //        head = head.next;
    //    }
    //    //双指针
    //    int red = 0;
    //    int green = list.size() - 1;
    //    while (green >= red) {
    //        if (list.get(red).subtract(list.get(green)).intValue() != 0) {
    //            return false;
    //        }
    //        red++;
    //        green--;
    //    }
    //    return true;
    //}
